/**
 * 78. 子集
 * https://leetcode-cn.com/problems/subsets/
 */

const { displayNestedArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number} begin
 * @param {number[]} cache
 * @param {number} top
 * @param {number[][]} total
 */
function sub(nums, begin, cache, top, total) {
  if (begin >= nums.length) return;
  cache[top] = nums[begin];
  total.push(cache.slice(0, top + 1));
  for (let i = begin + 1; i < nums.length; i += 1) {
    sub(nums, i, cache, top + 1, total);
  }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function subsets(nums) {
  const cache = new Array(nums.length).fill(0);
  const result = [[]];
  for (let i = 0; i < nums.length; i += 1) {
    sub(nums, i, cache, 0, result);
  }
  return result;
}

console.log(displayNestedArray(subsets([1, 2, 3])) === '[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]');
console.log(displayNestedArray(subsets([0])) === '[[],[0]]');
